import java.util.Comparator;
import java.util.TreeSet;

/**
 *
 *
 *   求最小区间
 *   N个集合，每个聚合取一个数，使得|N1-N2| + |N2-N3| +....+ |N3-N1| 最小。
 *   第一步简化问题：假设3个集合，最后取值分别是a,b,c 那么最小值是 |a-b| + |b-c| + |c-a|
 *   放在线段上，那就是2|min(a,b,c)-max(a,b,c)|
 *
 *   {1,5,6}
 *   {2,7,9}
 *   {4,6,8}
 *
 *
 */


public class Code01_MinRange {

    static class Node{
        int val;
        int ownIndex;
        int arrIndex;

        public Node(int val, int ownIndex, int arrIndex) {
            this.val = val;
            this.ownIndex = ownIndex;
            this.arrIndex = arrIndex;
        }
    }

    static int calculationMinRange(int[][] matrix) {
        TreeSet<Node> treeSet = new TreeSet<>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o1.val != o2.val ? o1.val - o2.val : o1.hashCode() - o2.hashCode();
            }
        });
        //最后set个数
        int N = matrix.length;

        //添加第一个
        for (int i = 0; i < N ;i++) {
            treeSet.add(new Node(matrix[i][0],0,i));
        }

        int minRange = Integer.MAX_VALUE;

        while( treeSet.size() == N){
            try {
                minRange =  Math.min(minRange,treeSet.last().val - treeSet.first().val);
            } catch (RuntimeException e) {

                System.out.printf("123");
            }

            Node node = treeSet.pollFirst();
            if(node.ownIndex + 1 <= matrix[node.arrIndex].length -1) {
                treeSet.add(new Node(matrix[node.arrIndex][node.ownIndex+1], node.ownIndex+1, node.arrIndex));
            }
        }

        return minRange;
    }

    public static void main(String[] args) {
        int[][] matrix = {{1,5,6},{2,7,9},{4,6,8}};
        int i = calculationMinRange(matrix);
        System.out.printf(String.valueOf(i));
    }
}
